<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="libman.css">
<TITLE>
Advanced Use of Eplex Instances
</TITLE>
</HEAD>
<BODY >
<A HREF="libman054.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman052.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="libman056.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc113">9.3</A>&nbsp;&nbsp;Advanced Use of Eplex Instances</H2><UL>
<LI><A HREF="libman055.html#toc60">Obtaining Solver State Information</A>
<LI><A HREF="libman055.html#toc61">Creating Eplex Instances Dynamically</A>
<LI><A HREF="libman055.html#toc62">Interface for CLP-Integration: Solver Demons</A>
<LI><A HREF="libman055.html#toc63">Encapsulated Modification of the Problem: Probing</A>
<LI><A HREF="libman055.html#toc64">Destroying the Solver State</A>
<LI><A HREF="libman055.html#toc65">Eplex Instance Interface Example: definition of optimize/2:</A>
</UL>

<A NAME="eplex-instance-advanced"></A>
<A NAME="toc60"></A>
<H3 CLASS="subsection"><A NAME="htoc114">9.3.1</A>&nbsp;&nbsp;Obtaining Solver State Information</H3>
<A NAME="eplex-instance-solver-info"></A>
The black-box interface binds both the objective value (Cost) and the
problem variables by bindings these variables. On the other hand, <B>eplex_solve/1</B> binds the objective value, but does not bind the problem
variables. These values can be obtained by:<BR>
<BR>

<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<A HREF="../bips/lib/eplex/eplex_var_get-3.html"><B>EplexInstance:eplex_var_get(+Var, +What, -Value)</B></A><A NAME="@default289"></A><DD CLASS="dd-description"><BR>
<BR>
Retrieve information about the solver state associated with the eplex
instance for the variable <TT>Var</TT>. If <TT>What</TT> is <TT>solution</TT> or
<TT>typed_solution</TT>, then the value assigned to this variable by the
solver state to obtain the optimal solution is returned in <TT>Value</TT>. <TT>solution</TT> returns the value as a float, and <TT>typed_solution</TT> returns the value as either a float or a rounded integer, depending
on if the variable was constrained to an integer in the eplex problem.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/eplex/eplex_get-2.html"><B>EplexInstance:eplex_get(+What, -Value)</B></A><A NAME="@default290"></A><DD CLASS="dd-description"><BR>
<BR>
Retrieve information about solver state associated with the eplex instance.
This returns information such as the problem type, the constraints for the
eplex problem. See the reference manual for more details.<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/eplex/eplex_set-2.html"><B>EplexInstance:eplex_set(+What, +Value)</B></A><A NAME="@default291"></A><DD CLASS="dd-description">
Set a solver option for the eplex instance. 
<DT CLASS="dt-description"><A HREF="../bips/lib/eplex/eplex_write-2.html"><B>EplexInstance:eplex_write(+Format, +File)</B></A><A NAME="@default292"></A><DD CLASS="dd-description">
Write out the problem in the the eplex instance's solver state to the file
File in format Format. The writing is done by the external solver. Use the
use_var_name(yes) option in
<A HREF="../bips/lib/eplex/eplex_solver_setup-4.html"><B>eplex_solver_setup/4</B></A><A NAME="@default293"></A>
so that the written file uses ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>variable names. Also the <TT>write_before_solve</TT> option of eplex_solver_setup/4 can be used to write out
a problem just before it is solved by the external solver: this allows
problem to be written in places where eplex_write/2 cannot be added
(e.g. for probing problems)..<BR>
<BR>
<DT CLASS="dt-description"><A HREF="../bips/lib/eplex/eplex_read-2.html"><B>EplexInstance:eplex_read(+Format, +File)</B></A><A NAME="@default294"></A><DD CLASS="dd-description">
Read a MP problem in the file File in format Format into a solver state,
and associate the solver with the eplex instance. No solver must already be
setup for the eplex instance. The solver state that is setup can only be
triggered explicitly.</DL>


So for the simple MIP example:
<PRE CLASS="verbatim">

:- lib(eplex).
:- eplex_instance(my_instance).

mip_example2([X,Y], Cost) :-
     my_instance: (X+Y $&gt;= 3),
     my_instance: (X-Y $= 0),
     my_instance: integers([X]),
     my_instance: eplex_solver_setup(min(X)),
     my_instance: eplex_solve(Cost),
     my_instance: eplex_var_get(X, typed_solution, X),
     my_instance: eplex_var_get(Y, typed_solution, Y).

....
[eclipse 2]: mip_example2([X,Y],C).

X = 2
Y = 2.0
C = 2.0

</PRE>
In the example, only X is returned as an integer, as Y was not explicitly
constrained to be an integer.<BR>
<BR>
Note that if there are multiple eplex instances, and a variable is shared
between the instances, then the solver state for each instance can have a
different optimal value to the variable.<BR>
<BR>
<A NAME="toc61"></A>
<H3 CLASS="subsection"><A NAME="htoc115">9.3.2</A>&nbsp;&nbsp;Creating Eplex Instances Dynamically</H3>
<A NAME="@default295"></A>
So far, we have shown the use of <TT>eplex_instance/1</TT> as a directive to
declare an eplex instance. For some applications, it might be necessary to
create eplex instances dynamically at run-time. The can be done by calling
<TT>eplex_instance/1</TT> at run-time.
In this case, the instance name should <EM>not</EM> be used to module-qualify
any predicates in the code, since this will raise a compiler warning
complaining about an unknown module.
<PRE CLASS="verbatim">
   new_pool(X,Y) :-  % INCORRECT
      eplex_instance(pool),
      pool: (X $&gt;= Y), % will generate a warning
      ...
</PRE>Of course, in the above code, the instance name <TT>pool</TT> is already known
at compile time, so it can always be declared by a directive.<BR>
<BR>
If the name is truly generated dynamically, this can be done as follows:
<PRE CLASS="verbatim">
   new_pool(Pool,X,Y) :-
       eplex_instance(Pool),
       Pool: (X $&gt;= Y),
       ....
</PRE>

<H4 CLASS="subsubsection">Obtaining Bounds on the Objective Value</H4>
The external solver does not always return the optimal objective
value, for example when the optimisation was aborted. However, even when
the solver returns an optimal solution, it may actually not be the exact
optimal, because of solver settings (e.g. for MIP problems, the MIP search
will terminate when the solution found is within certain tolerance of the
best possible solution value). In these cases, it may be useful to obtain
some bounds on the optimal objective value. The best and worst bounds on
the optimal objective can be obtained using the best_bound and worst_bound
options of <A HREF="../bips/lib/eplex/eplex_get-2.html"><B>eplex_get/2</B></A><A NAME="@default296"></A>,
respectively. <BR>
<BR>
<A NAME="toc62"></A>
<H3 CLASS="subsection"><A NAME="htoc116">9.3.3</A>&nbsp;&nbsp;Interface for CLP-Integration: Solver Demons</H3>
To implement hybrid algorithms where a run of a simplex/MIP solver is only
a part of the global solving process, the black-box model presented above
is not appropriate anymore. With eplex instances, we can call <TT>eplex_solve/1</TT> repeatedly to re-solve the problem, perhaps after adding
more constraints to the problem or after changes in the variable
bounds. However, the solver must be invoked explicitly. We require more
sophisticated methods of invoking the solver. This can be done by setting
up a solver demon, and specifying the conditions in which the demon is to
wake up and invoke the external solver.<BR>
<BR>

<H4 CLASS="subsubsection"><A HREF="../bips/lib/eplex/eplex_solver_setup-4.html"><B>EplexInstance:eplex_solver_setup(+Objective, -Cost, +ListOfOptions, +TriggerModes)</B></A><A NAME="@default297"></A></H4>
This is a more sophisticated set up for a new solver state than
<TT>eplex_solver_setup/1</TT> (in fact eplex_solver_setup/1 is a special case
of eplex_solver_setup/4).
The main idea is that a list of trigger conditions
are specified in <TT>TriggerModes</TT>, and along with setting up the solver
state, a demon goal is created which is woken up when one of the
specified trigger condition is met. This demon goal will then invoke the
solver, with any 
constraints posted to the eplex instance since the solver was last invoked
taken into account, to re-solve the problem. <BR>
<BR>
The <TT>ListOfOptions</TT> is a list of solver options for setting up the
solver state. Some of these affect the way the external solver solves the
problem, such as if presolve should be applied before solving the problem.
See the reference manual for <A HREF="../bips/lib/eplex/eplex_solver_setup-4.html"><B>eplex_solver_setup/4</B></A><A NAME="@default298"></A> for
details on the available options and trigger modes.<BR>
<BR>
As the solver is designed to be invoked repeatedly, it is inappropriate to
directly bind <TT>Cost</TT> to the objective value. Instead, the objective
value is exported as a bound to Cost:
For a minimisation problem, each solution's
cost becomes a lower bound, for maximisation an upper bound on Cost.
This technique allows for repeated re-solving with reduced variable bounds
or added constraints. Note that the bound update is done only if the
solution is optimal. Note also that Cost is not automatically 
made a problem variable, and thus may not have bounds associated
with in. In order for the bounds information not to be lost, some bounds
should be given to Cost (e.g. making it a problem variable (but
this might introduce unnecessarily self-waking on bounds change), or via
another solver with bounds (e.g. ic)). <BR>
<BR>
<A NAME="@default299"></A>
Note that when a solver demon runs frequently on relatively small problems,
it can be important for efficiency to switch the external solver's
presolving off for this demon as part of the <TT>ListOfOptions</TT> during the
setup of the problem to reduce overheads.<BR>
<BR>

<H4 CLASS="subsubsection">Example</H4>
The simplest case of having a simplex solver automatically cooperating
with a CLP program, is to set up a solver demon which will repeatedly
check whether the continuous relaxation of a set of constraints
is still feasible.
The code could look as follows (we use the eplex instance in this example):
<PRE CLASS="verbatim">
simplex :-
    eplex:eplex_solver_setup(min(0), C, 
        [solution(no)], [bounds]).
</PRE>First, the constraints are normalised and checked for linearity.
Then a solver with a dummy objective function is set up. The option
<TT>solution(no)</TT> indicates that we are not interested in solution values.
Then we start a solver demon which will re-examine the problem
whenever a change of variable bounds occurs.
The demon can be regarded as a compound constraint implementing the
conjunction of the individual constraints. It is able to detect
some infeasibilities that for instance could not be detected by a
finite domains solver, e.g.
<PRE CLASS="verbatim">
[eclipse 2]: eplex:(X+Y+Z &gt;= K), eplex:(X+Y+Z =&lt; 1),
    eplex:eplex_solver_setup(min(0), C, 
        [solution(no)], [bounds]),
    K = 2.

No (0.00s cpu)
</PRE>In the example, the initial simplex is successful, but instantiating
K wakes the demon again, and the simplex fails this time.<BR>
<BR>
A further step is to take advantage of the cost bound that the simplex
procedure provides. To do this, we need to give the objective 
The setup is similar to above, but we accept an objective function and
add a cost variable. The bounds of the cost variable will be updated
whenever a simplex invocation finds a better cost bound on the problem.
In the example below, an upper bound for the cost of 1.5 is found
initially:
<PRE CLASS="verbatim">
[eclipse 5]: ic: (Cost $:: -1.0Inf..1.0Inf), 
      eplex:(X+Y $=&lt; 1), eplex:(Y+Z $=&lt; 1), eplex:(X+Z $=&lt; 1),
      eplex:eplex_solver_setup(max(X+Y+Z), Cost, 
          [solution(no)], [bounds]).

X = X{-1e+20 .. 1e+20}
Y = Y{-1e+20 .. 1e+20}
Z = Z{-1e+20 .. 1e+20}
Cost = Cost{-1.0Inf .. 1.500001}


Delayed goals:
        lp_demon(prob(...), ...)
Yes (0.00s cpu)
</PRE>(Note that the ranges for X, Y and Z is -1e+20 .. 1e+20 as 1e+20 is this
external solver's notion of infinity). <BR>
<BR>
If the variable bounds change subsequently, the solver will be re-triggered,
improving the cost bound to 1.3:
<PRE CLASS="verbatim">
[eclipse 6]: ic: (Cost $:: -1.0Inf..1.0Inf), 
      eplex:(X+Y $=&lt; 1), eplex:(Y+Z $=&lt; 1), eplex:(X+Z $=&lt; 1),
      eplex:eplex_solver_setup(max(X+Y+Z), Cost, 
          [solution(no)], [bounds]), 
      eplex:(Y =&lt; 0.3).

X = X{-1e+20 .. 1e+20}
Z = Z{-1e+20 .. 1e+20}
Cost = Cost{-1.0Inf .. 1.300001}
Y = Y{-1e+20 .. 0.3}


Delayed goals:
        lp_demon(prob(...), ...)
Yes (0.00s cpu)
</PRE>
A further example is the implementation of a MIP-style branch-and-bound
procedure. Source code is provided in the library file mip.pl.<BR>
<BR>
<A NAME="toc63"></A>
<H3 CLASS="subsection"><A NAME="htoc117">9.3.4</A>&nbsp;&nbsp;Encapsulated Modification of the Problem: Probing</H3>
The external mathematical programming solvers often provides the facility
for the user to change the problem being solved. This includes the addition
or removal of constraints, and the changing of the objective function.
We have already seen how extra constraints can be added. As ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> is a
logic programming language, removal of constraints is automatically
achieved by backtracking. We do not allow the user to explicitly remove
constraints that have been collected by the external solver, as this makes 
the problem non-monotonic.
For the same reason, we do not allow the objective function to be
changed.<SUP><A NAME="text6" HREF="libman052.html#note6">1</A></SUP>
However, we do allow the problem (including the objective function) to be
<I>temporarily</I> changed in certain specified ways. This allows the
problem to be `probed' with these changes:<BR>
<BR>

<H4 CLASS="subsubsection"><A HREF="../bips/lib/eplex/eplex_probe-2.html"><B>EplexInstance:eplex_probe(+Probes, -Cost)</B></A><A NAME="@default300"></A></H4>
Similar to eplex_solve/1, but the problem is first temporarily modified as
specified in Probes before the optimisation. The Cost value
is instantiated to the objective value for this new modified problem, and
any solution state requested are also updated. <BR>
<BR>
<A NAME="toc64"></A>
<H3 CLASS="subsection"><A NAME="htoc118">9.3.5</A>&nbsp;&nbsp;Destroying the Solver State</H3>

<H4 CLASS="subsubsection"><A HREF="../bips/lib/eplex/eplex_cleanup-0.html"><B>EplexInstance:eplex_cleanup</B></A><A NAME="@default301"></A></H4>
Destroy the specified solver, free all memory, etc.
Note that ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> will normally do the cleanup automatically,
for instance when execution fails across the solver setup, or
when a solver handle gets garbage collected. The solver is disassociated
with the eplex instance, and any outstanding constraints not yet collected
by the solver are removed, with a warning to the user. In effect, the
eplex instance is reinitialised.<BR>
<BR>
Note that this is a non-logical operation. Backtracking into code before 
<TT>eplex_cleanup/0</TT> will not restore the solver state, and any attempt to
reuse the solver state will not be possible (the execution will abort with
an error). Normally, it is recommended to let ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> perform the cleanup 
automatically,
for instance when execution fails across the solver setup, or
when an unused solver state handle gets garbage collected.
However, calling eplex_cleanup/0 may
cause resources (memory and licence) to be freed earlier.<BR>
<BR>
<A NAME="toc65"></A>
<H3 CLASS="subsection"><A NAME="htoc119">9.3.6</A>&nbsp;&nbsp;Eplex Instance Interface Example: definition of optimize/2:</H3>
<A NAME="defoptimize"></A>
A black-box setup-and-solve predicate <B>optimize/2</B> can be defined as:
<PRE CLASS="verbatim">
optimize(OptExpr, ObjVal) :-
        eplex:eplex_solver_setup(OptExpr),
        eplex:eplex_solve(ObjVal),
        eplex:eplex_get(vars, VArr),
        eplex:eplex_get(typed_solution, SolutionVector),
        VArr = SolutionVector,                  % do the bindings
        eplex:eplex_cleanup.
</PRE>A solver state is set up for the eplex instance <TT>eplex</TT>, to allow
constraints that were previously posted to <TT>eplex</TT> to be collected.
This happens once the solver is invoked by <TT>eplex_solve/1</TT>. If there
is a solution, the solution vector is obtained, and the
variables are instantiated to those solutions.<BR>
<BR>
<HR>
<A HREF="libman054.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="libman052.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="libman056.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
